package org.example.tree;

public class ClueTree extends BinaryTree{

    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre 总是保留前一个结点
    private ClueNode pre = null;

    public void threadedNodes(){
        this.threadedNodes(super.getRoot());
    }

    //遍历线索化二叉树的方法
    public void threadedList(){
        ClueNode node = (ClueNode) super.getRoot();
        while(node != null){
            while(node.getLeftType() == 0){
                node = (ClueNode) node.getLeft();
            }
            //打印当前节点
            System.out.println(node);
            while(node.getRightType() == 1){
                node = (ClueNode) node.getRight();
                System.out.println(node);
            }
            //如果当前节点的右指针指向的后继节点，就一直输出
            node = (ClueNode) node.getRight();
        }
    }

    public void threadedNodes(HeroNode node){

        if (node instanceof ClueNode) {
            ClueNode clueNode = (ClueNode) node;

            /**
             * 1.线索化左子树
             * 2.线索化当前节点
             * 3.线索化右子树
             * */
            threadedNodes(clueNode.getLeft());

            if (clueNode.getLeft() == null){
                //让当前节点的左指针指向前驱节点
                clueNode.setLeft(pre);
                //修改当前节点的左指针的类型，指向前驱节点
                clueNode.setLeftType(1);
            }
            if (pre != null && pre.getRight() == null){
                //让前驱节点的右指针指向当前节点
                pre.setRight(clueNode);
                //修改前驱节点的右指针类型
                pre.setRightType(1);
            }
            //每处理一个节点后，让当前节点等于下一个节点的前驱节点
            pre = clueNode;

            threadedNodes(clueNode.getRight());
        }

    }

}

